package tep;

import java.util.Random;

public class ch3 {
    
    public static void fun1(int[] arr){
        
        dfs(arr,0,arr.length-1);
        
    }

    private static void dfs(int[] arr, int start, int end) {
        if(start<end){
            int p = portion(arr,start,end);
            dfs(arr,start,p-1);
            dfs(arr,p+1,end);
        }
        
    }

    private static int portion(int[] arr, int start, int end) {
        int p = new Random().nextInt(end-start)+start;
        int num = start;
        swap(arr,p,end);
        for(int i=start;i<end;i++){
            if(arr[i]<arr[end]){
                swap(arr,num,i);
                num++;
            }
        }
        swap(arr,num,end);

        return num;

    }

    private static void swap(int[] arr, int num1, int num2) {
        int n1 = arr[num1];
        arr[num1] = arr[num2];
        arr[num2] = n1;
    }


    public static void main(String[] args) {

        int[] arr = new int[]{2,1,4,5,5,1,10,9};
        fun1(arr);
        System.out.println(" ");
        for (int i:arr){
            System.out.print(i+" ");
        }

    }


}
